class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        length1 = len(s)
        length2 = len(p)
        dp = [[False for _ in range(length2+1)] for _ in range(length1+1)]
        dp[0][0] = True
        for i in range(1, length1+1):
            for j in range(1, length2+1):
                if s[i-1] == p[j-1]:
                    dp[i][j] |= dp[i-1][j-1]
                if p[j-1] == '.':
                    dp[i][j] |= dp[i-1][j-1]
                if p[j-1] == '*':
                    if i >= 2 and s[i-1] == s[i-2]:
                        dp[i][j] |= dp[i][j-1]
                    dp[i][j] |= dp[i-1][j] & dp[i][j-1] & dp[i-1][j-1]
        return dp[length1][length2]

if __name__ == '__main__':
    s = Solution()
    r = s.isMatch("abbc","ab*c")
    print(r)